package search.binarysearch;

import java.util.Arrays;

/**
 * 常规二分法查找
 *
 * @author xushijian
 * @date 2021/10/14 12:34
 */
public class CommonBinaryTest {

    public static void main(String[] args) {
        //定义一个数组
        int[] arr = {2, 8, 74, 687, 9, 4, 7, 687, 456, 3214674, 68, 4852};
        //二分法查找必须是有序数组，否则无法完成二分法查找
        //先给数组进行排序
        Arrays.sort(arr);
        //遍历数组，为了试验结果
        System.out.println(Arrays.toString(arr));
        //调用方法，查询需要值
        System.out.println(ArrayDichotomy(arr, 4852));
    }

    /**
     * 使用二分法查找数组中的数据,并返回数据在数组中的位置（数组下标）
     *
     * @param arr    数组
     * @param number 数值
     */
    public static int ArrayDichotomy(int arr[], int number) {

        //定义查询范围的最小值,第一个查询数应该是从零开始
        int min = 0;
        //定义查询范围的最大值，第一次查询应该是数组的长度
        int max = arr.length - 1;
        //定义查询数据所在的位置，用来二分计数,二分计算应该是最大值加上最小值的和除以2
        int mid = 0;
        while (min + 1 < max) {
            mid = (max + min) / 2;
            if (number == arr[mid]) {
                return mid;
            }
            //二分判断，如果需要查找的数字，大于数组中间数，则结果值应该在数组的后半段，反而反之
            if (number > arr[mid]) {
                //如果在后半段，则移动最小值到当前的中间数的后一位
                min = mid + 1;
            }
            //如果查询数小于中间数，则在前半段
            if (number < arr[mid]) {
                //在前半段，则移动最大数到中间值的前一位
                max = mid - 1;
            }
        }
        //超出数组，查无此数
        System.out.println("查无此数！");
        return -1;
    }

}